Many zero-knowledge identification protocols are known. Among others, the four following protocols may be cited:
1) The Fiat-Shamir protocol described in: A. Fiat and A. Shamir, “Howe to prove yourself: Practical solutions to identification and signature problems”, published in Advances in Cryptology; Proceedings of Crypto '86, Lecture Notes in Computer Science, vol. 263, Springer-Verlag, Berlin, 1987, pp. 186–194;
2) The Guillou-Quisquater protocol described in: L. C. Guillou and J. J. Quisquater, “A practical zero-knowledge protocol fitted to security microprocessors minimizing both transmission and memory”, published in Advances in Cryptology: Proceedings of Eurocrypt '88, Lecture Notes in Computer Science, vol. 330, Springer-Verlag, Berlin, 1988, pp. 123–128;
3) The Schnorr protocol described in: C. P. Schnorr, “Efficient identification and signatures for smart cards”, published in Advances in Cryptology: Proceedings of Crypto '89, Lecture Notes in Computer Science, vol. 435, Springer-Verlag, Berlin, 1987, pp. 239–252;
4) The Girault protocol described in French patent application FR-A-2 716 058.
In general, most zero-knowledge authentication protocols are performed in 4 stages. In order to simplify matters, it will be supposed that the authenticating entity, called B, already knows all the public parameters that are characteristic of the entity to be authenticated, called A, in other words its identity, public key, etc. The four stages are then as follows:
Stage 1:
A provides B with at least one commitment c consisting either of a parameter x chosen at random by A or of a pseudo-random function h of parameter x and, if appropriate, the message to be authenticated or signed: c=h (x, [M]), (the notation [M] signifies that M is optional).
Stage 2:
B selects a parameter e called “question” at random and transmits e to A.
Stage 3: A provides B with a response y, which is coherent with question e, commitment c and public key v of A.
Stage 4: B computes x from elements y, e and v, i.e. x=φ(y, e, v) then checks that: c=h(φ(v, e, y), [M]).
In certain protocols there are one or two additional exchanges between A and B. For message signatures, the two initial exchanges are eliminated and parameter e is selected equal to c: A only computes successively c, e (i.e. c) and y.
The number u of questions that can be selected by B is linked directly to the security level of the protocol on which the probability of success of an imposter (i.e. an entity C that makes a fraudulent attempt to pretend to be A) is dependent. The security level, which is called p, is characterized by a parameter k according to the relation p=1−2−k. In other words, imposters have only one chance in 2k of carrying out their imposture successfully. It may be proved that if the protocol is based on a difficult mathematical problem and if the commitments are of sufficient length then the length of u must be equal to k bits. In other words, the question must be selected from the set {0, . . . , 2k−1} (including limiters).
In the background art k is equal to 32 bits, which gives only one chance in four billion of an imposture being successful. In applications where identification failure can have very damaging consequences, such as prosecution, the length may be reduced to several bits.
None of the above-mentioned protocols can be implemented in the basic version in high-requirement applications, such as those described above, because the computing operations required cannot be performed by a smart card that is not equipped with a cryptographic coprocessor.
A first optimization, introduced by Fiat and Shamir, concerns the number of bits exchanged between the two entities. Said optimization consists in using a hash function in the computing operation of the commitment. The optimization itself does not reduce the number of computing operations performed by the authenticated entity because the commitment continues to be computed by the optimization.
In order to reduce the number of computing operations a particular procedure, called a pre-computation mode, must be used that consists in computing in advance the parameters, called pre-commitments, that are included in the computing operation of the commitments. The commitments can also be computed by a server with greater computing power and then stored in the smart card of the entity to be authenticated. When the electronic transaction actually takes place the smart card has only rudimentary computing operations to perform. This operating procedure is disclosed in French patent application FR-A-2 716 058 cited above. Each pre-commitment is used for one transaction only. When all the pre-commitments have been consumed by the card it is necessary to compute new ones and store them in the card (recharging operation).
Since the data memory of an inexpensive smart card rarely exceeds 8 Kbytes, it is difficult to imagine dedicating more than 1 Kbyte to storing pre-commitments alone. It is therefore necessary to reduce the size of said pre-commitments to a minimum in order to perform a maximum number of transactions between two recharges.
In all these authentication methods a computing operation capacity may be defined that is the maximum number of computing operations that the implemented means can perform in a reasonable time. As the computing operations are binary the capacity may be expressed as a power of 2, for example 2N where N is an integer. The number is not determined with great accuracy but is defined to within a few units. For example, at present integer N is of the order of approximately 80, in other words with only the means available the capacity is 280, i.e. a maximum of approximately 280 operations may be performed in a reasonable time.
In the basic version of the method described in French patent application FR-A-2 716 058 cited above, the size of the pre-commitments or the commitments themselves is approximately 2N bits where number N is equal to approximately 80. The size of a pre-commitment is therefore approximately 160 bits (it is 128 bits in the document cited above where N is taken as 64). Fifty commitments can therefore be stored in a 1-Kbyte memory, which is relatively few.
In another French patent application FR-A-2 752 122 an authentication method is described that reduces the number of bits to be transmitted or stored. The size of the pre-commitments or commitments can be reduced to a little more than N bits, i.e. approximately 88 if N=80, which enables more than 90 pre-commitments to be stored in a 1-Kbyte memory and to reduce the bits transmitted to 18% when the protocol is performed.
Unfortunately, this gain remains insufficient for many applications, particularly for the electronic wallet. Many transactions may only concern very small amounts, such as for public transport, parking meters, local telecommunications, etc., and the user must be able to perform transactions until the credit runs out without being limited by any other consideration. In this context, a minimum 150 to 200 transactions without recharge would appear to be required, which the known methods do not allow.
The aim of the present invention is precisely to further reduce the size of the pre-commitments and, optionally, the commitments themselves. According to the invention the number of bits can be reduced to approximately 48 which enables 170 pre-commitments to be stored in a 1-Kbyte memory. In certain applications the size may be even smaller and, for example, be reduced to 32 bits which enables 256 pre-commitments to be stored.
The invention therefore enables quick performance of an algorithm of identification or authentication of a message or signature of a message in an inexpensive smart card for applications such as electronic wallets or future generation telephone cards.